package LeetCode.month01.day27;

public class No2156 {
    public static void main(String[] args) {
        System.out.println(subStrHash("fbxzaad",31,100,3,32));
    }
    public static String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] c = s.toCharArray();
        int n = c.length;
        long sum = 0;
        int res = 0;
        long pow = 1;
        for (int i = n-1; i >=n-k ; i--) {
            sum = (sum*power+(c[i]-'a'+1))%modulo;
            pow = pow*power%modulo;
        }
        if(sum==hashValue) res=n-k;
        for (int i = n-k-1; i >=0; i--) {
            sum = (sum*power+c[i]-'a'+1-(c[i+k]-'a'+1)*pow%modulo+modulo)%modulo;
            if(sum==hashValue) res = i;
        }
        return s.substring(res,res+k);


        //正序溢出
//        int n = s.length();
//        char[] chars = s.toCharArray();
//        long num = 0;
//        for (int i = 0; i < k-1; i++) {
//            num+=(chars[i]-'a'+1)*(int)Math.pow(power,i);
//            System.out.println(num);
//        }
//        for (int i = k-1; i < n; i++) {
//            System.out.print("num="+num+"+"+(chars[i]-'a'+1)+"*"+(int)Math.pow(power,k-1));
//            num+=(chars[i]-'a'+1)*(int)Math.pow(power,k-1);
//            System.out.println("="+num);
//            System.out.println(num%modulo);
//            if(num%modulo==hashValue) return s.substring(i-k+1,i+1);
//            num=(num-(chars[i-k+1]-'a'+1))/power;
//        }
//        return "";
    }
}
